Navigation and routing service providers are continually challenged to provide new and compelling services. One area of development relates to creating more personalized or customizable routing options. For example, typically when a traveler requests a navigation or routing service, a path that satisfies certain cost preferences or constraint parameters (e.g., shortest distance, shortest travel time, etc.) is returned. However, in some cases, the traditionally calculated path may not meet the traveler's needs or preferences. The user of the navigation service or system may then want an alternative path that is different from an originally planned path and yet meets the originally specified cost preference or constraint parameter. Depending on the complexity of the path, computing such an alternative path can require significant computational resources. Accordingly, service providers face significant technical challenges to enabling the computation of such alternative paths using minimal computational resources.